package bishi._58tongcheng;

import java.util.Arrays;

/**
 * @author: Tangxz
 * @email: 1171702529@qq.com
 * @cate: 2021/09/25 20:00
 */
public class three {
    public static void main(String[] args) {
        three t = new three();
        for (boolean b : t.pathAvailable(new int[][]{{1, 1, 1, 1}, {0, 0, 0, 0}, {1, 1, 1, 1}, {1, 1, 0, 1}}, new int[][]{{0, 0}, {0, 1}, {2, 0}}, new int[][]{{0, 3}, {2, 2}, {3, 3}})) {
            System.out.print(b+",");
        }
    }
    

    
    int[][] part = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};

    public boolean[] pathAvailable (int[][] matrix, int[][] starts, int[][] ends) {
        // write code here
        // 题目描述是灰色？！！！！建议增加一点用户体验，看着这颜色很累
        if(matrix.length==0||matrix[0].length==0)return new boolean[0];
        boolean[] res = new boolean[starts.length];
        for(int i=0;i<starts.length;i++){
            boolean[][] temp = new boolean[matrix.length][matrix[0].length];
            for(boolean[] t:temp){
                Arrays.fill(t,false);
            }
            res[i] = dfs(matrix,starts[i],ends[i],temp);
        }
        return res;
    }

    public boolean dfs(int[][] matrix,int[] start,int[] end,boolean[][] temp){
        if(start[0]==end[0]&&start[1]==end[1]) return true;
        boolean res = false;
        for(int[] p:part){
            int startX = start[0]+p[0];
            int startY = start[1]+p[1];
            if(startX<0||startX>=matrix.length||startY<0||startY>=matrix[0].length||matrix[startX][startY]==0||temp[startX][startY])
                continue;
            temp[startX][startY] = true;
            res|=dfs(matrix,new int[]{startX,startY},end,temp);
        }
        return res;
    }
}
